|
In number theory and enumerative combinatorics, the ordered Bell numbers or Fubini numbers count the number of weak orderings on a set of ''n'' elements (orderings of the elements into a sequence allowing ties, such as might arise as the outcome of a horse race).〔. Because of this application, de Koninck calls these numbers "horse numbers", but this name does not appear to be in widespread use.〕 Starting from ''n'' = 0, these numbers are :1, 1, 3, 13, 75, 541, 4683, 47293, 545835, 7087261, 102247563, ... . The ordered Bell numbers may be computed via a summation formula involving binomial coefficients, or by using a recurrence relation. Along with the weak orderings, they count several other types of combinatorial objects that have a bijective correspondence to the weak orderings, such as the ordered multiplicative partitions of a squarefree number〔 or the faces of all dimensions of a permutohedron〔.〕 (e.g. the sum of faces of all dimensions in the truncated octahedron is 1 + 14 + 36 + 24 = 75〔1, 14, 36, 24 is the fourth row (of this triangle ) 〕). ==History== The ordered Bell numbers appear in the work of , who used them to count certain plane trees with ''n'' + 1 totally ordered leaves. In the trees considered by Cayley, each root-to-leaf path has the same length, and the number of nodes at distance ''i'' from the root must be strictly smaller than the number of nodes at distance ''i'' + 1, until reaching the leaves.〔. In (''Collected Works of Arthur Cayley'', p. 113 ).〕 In such a tree, there are ''n'' pairs of adjacent leaves, that may be weakly ordered by the height of their lowest common ancestor; this weak ordering determines the tree. call the trees of this type "Cayley trees", and they call the sequences that may be used to label their gaps (sequences of ''n'' positive integers that include at least one copy of each positive integer between one and the maximum value in the sequence) "Cayley permutations".〔.〕 traces the problem of counting weak orderings, which has the same sequence as its solution, to the work of .〔〔. As cited by .〕 These numbers were called Fubini numbers by Louis Comtet, because they count the number of different ways to rearrange the ordering of sums or integrals in Fubini's theorem, which in turn is named after Guido Fubini.〔.〕 For instance, for a bivariate integral, Fubini's theorem states that : where these three formulations correspond to the three weak orderings on two elements. In general, in a multivariate integral, the ordering in which the variables may be grouped into a sequence of nested integrals forms a weak ordering. The Bell numbers, named after Eric Temple Bell, count the number of partitions of a set, and the weak orderings that are counted by the ordered Bell numbers may be interpreted as a partition together with a total order on the sets in the partition.〔.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ordered Bell number」の詳細全文を読む スポンサード リンク
|